1. Field of the Invention
The invention relates generally to computer data storage and communication error detection and correction methods and devices, and more specifically to dedicated microcode processors that are optimized for on-the-fly Galois field Reed-Solomon error correction code operations in hard disk drives.
2. Description of the Prior Art
The recording and readback of every bit in a sector on a hard disk drive cannot be perfect, given practical error rates. So various error detecting and correcting schemes are employed to transparently bridge over the data errors that will occur when accessing the physical medium. This basically involves an overhead that is written into each sector that will help in the detecting and correcting of errors in the data fields during playback. The best such schemes do not impose an access delay that can slow down disk operations, nor do they load a computational overhead on the host processor. In other words, the ideal schemes are transparent to the host in terms of data latency and management overhead.
Reed-Solomon (RS) error correction codes are widely used in modern digital electronics systems such as compact disk players and satellite communication links. Reed-Solomon codes rely on doing arithmetic in finite, or Galois, fields. A particular field, GF(2.sup.8), is of central importance for many practical systems. The most elementary operations in Reed-Solomon decoders are multiplication and inversion. As a result, the time such Galois field operations take to execute and the resources dedicated to their operation are very critical.
Finite fields have many applications in error control coding. Error control coding is, in turn, very important in many communications applications to maintain the integrity of data being transmitted between remote locations. Finite fields are also used in digital signal processing, psuedorandom number generation, and the encryption and decryption protocols basic to cryptography.
For error control coding, the most common decoding procedure for a "t-error" correcting Reed-Solomon code consists of calculating the syndrome values, determining the error locator polynomial using algorithms such as Berlekamp's iterative algorithm or the Modified Euclid's algorithm, solving for the roots of the error locator polynomial, and computing the error magnitudes using methods such as Forney's algorithm.
The most computationally intensive step is determining the error locator polynomial because it involves extensive multiplication and inversion as "t" increases. Addition is a relatively simple operation, however multiplication, inversion, and exponentiation are more complex operations. Therefore as the demand for faster data transfers with error detection and correction increases, the design of efficient, high performance circuits to perform finite field arithmetic operations is gaining more attention.
Efficient architectures for error detection and decoding of Reed-Solomon encoded data can do their arithmetic operations in the Galois field. C. Y. Wang at the University of Minnesota (cywang@ee.umn.edu) reports having developed a new architecture to perform an operation like, AB +C, in a finite field. Such architecture internally represents the elements as powers of the primitive element. The proposed architecture supposedly has a low latency, compared to the other architectures. However, because of the exponential dependence of the hardware complexity on m in GF(2.sup.m), it is hardware efficient only for small finite Galois fields.
For larger finite fields, the University of Minnesota developed a parallel-in-parallel-out, bit-level pipelined multiplier architecture. Such architecture is said to reduce the overall area and decreases the system latency, as compared to the other proposed architectures. Utilizing the same approach, the University of Minnesota also developed a new parallel-in-parallel-out, bit-level pipelined architecture which performs squaring operations in finite field. The squarer is said to be 25% more hardware efficient than using a dedicated multiplier, and also has a lower system latency. The multiplier and squarer can be used in the square and multiply algorithm for exponentiation and yield an architecture with a claimed 12.5% hardware savings over the more current design and also have a lower system latency. The proposed architecture is easily implementable in VLSI because of its regular interconnection pattern, modular structures and concurrent operations. On the Internet, the University of Minnesota suggested for further reading on this subject, Surendra K. Jain and Kesha K. Parhi, "A Low Latency Standard Basis GF(2 M) Multiplier", 1995 International Conference on Acoustics, Speech, and Signal Processing, (Detroit, Mich.), May 1995; and. Surendra K. Jain and Kesha K. Parhi, "Efficient Power Based Galois Field Arithmetic Architectures", 1994 Workshop on VLSI Signal Processing, November 1994.
High levels of recording system performance and data reliability are now being attained by using a balanced combination of modulation coding and error-correcting coding (ECC). Coded modulation combines the functions of modulation and coding for a significant "coding gain" over conventional systems, which in some cases can exceed six decibels. The design engineer can then use this gain to increase areal density, increase transfer rate, or optimize performance in a number of other economically advantageous ways. The Reed-Solomon codes form the single most important class of error-correcting codes for use in data recording systems. Reed-Solomon codes efficiently correct random errors, long burst errors, multiple short bursts, and combinations of bursts and random errors.
Because disk drive areal densities have been increasing, the Quantum Corporation (Milpitas, Calif.) EUROPA 540/810/1080 AT hard disk drive series implements 160-bit Reed-Solomon single, double and triple burst Reed-Solomon error correction techniques to reduce the uncorrectable read error rate to less than one bit in every 10.sub.14 bits read. Single burst errors up to twenty-four bits per sector, and double burst errors up to forty-eight bits per sector are corrected on-the-fly, to improve data integrity and lessen any impact on the disk drive's performance. Because errors corrected on-the-fly do not require the drive to re-read the sector during the next revolution of the disk, such ECC correction is transparent to the host system. When errors cannot be corrected on-the-fly, an automatic retry and a more rigorous triple burst correction algorithm is used. Such measures can correct sectors with three bursts of up to twenty-four incorrect bits each, or up to nine multiple random one-byte burst errors. The Quantum EUROPA AT drives double check the main ECC correction with a cross-check code and algorithm to reduce the probability of primary ECC system miscorrection. Each sector in the Quantum EUROPA AT hard disk drive has 512 bytes of user data followed by two cross-check (XC) bytes, followed by eighteen ECC check bytes. The two cross-check bytes are used to double check the main ECC correction. As is conventional, the eighteen ECC check bytes are used to detect and correct errors, and the cross-check and ECC data are computed and appended to the user data when the sector is first written.